
%
%  $Description: Project proposal for MushAI$ 
%
%  $Date: 2010 $
%

\documentclass[times, 10pt,twocolumn]{article} 
\usepackage{proposal}
\usepackage{times}
\usepackage{url}

%\documentstyle[times,art10,twocolumn,proposal]{article}

%------------------------------------------------------------------------- 
% take the % away on next line to produce the final camera-ready version 
\pagestyle{empty}

%------------------------------------------------------------------------- 
\begin{document}

\title{MushAI: Project proposal (group 8)}

\author{Hans Andersson\\
MPSEN-1\\anhans@student.chalmers.se\\
% For a paper whose authors are all at the same institution, 
% omit the following lines up until the closing ``}''.
% Additional authors and addresses can be added with ``\and'', 
% just like the second author.
\and
Erik Axelsson\\
TKITE-3\\
erikax@student.chalmers.se\\
\and
Erik Levin\\
MPSEN-1\\
levine@student.chalmers.se
\and
Max Ocklind\\
MPIDE-1\\
ocklind@student.chalmers.se
}

\maketitle
\thispagestyle{empty}


%------------------------------------------------------------------------- 
\Section{Introduction}

The goal of this project is to explore how genetic programming can be used to develop an artificial intelligence that plays the board game Traverse.

Traverse is a so called abstract strategy board game, that is, a game with perfect information and no elements of chance or negotiation. The full game of Traverse is for two to four players, but we will only consider two player variant. The gameplay can be described as a combination between chess and Chinese checkers. Each player controls eight pieces of four different types, initially positioned along one edge of the board of 10 x 10 squares. Players take turns moving one of their pieces, and the goal is to be the first to reach the opposite side of the board with all pieces. Each type of piece is restricted to movement along certain directions, similar to chess, and pieces can jump over others in a manner pertaining to Chinese checkers \cite{rules}.

Genetic programming is a special case of genetic algorithms \cite{course_book} (pp. 116--119), where a population of computer programs is gradually evolved during a number of generations in resemblance of evolution in nature. The individuals that according to a fitness function are deemed best fitted for the problem are selected to combine into the individuals of the next generation. \cite{gpiv} provides a few examples of practical uses of genetic programming.

%------------------------------------------------------------------------- 
\Section{Key ideas}

\SubSection{What do you propose to do?}

We aim to develop an artificial intelligence that plays Traverse reasonably well. It should at least play significantly better than random playing (i.e. win practically every time), and ideally be as good as an amateur human player. Initially we will work with a smaller board with fewer types of pieces.

If the task is deemed infeasible to carry out with genetic programming we will instead use a more conventional search method such as minimax tree. Initially we will study both approaches in parallel.

%------------------------------------------------------------------------- 
\SubSection{What interesting and related things are outside the scope of your project?}

There will probably not be time to compare the genetic programming approach with agents developed through other methods, so this is outside of the scope as well. However, if time permits, we might develop another type of algorithm such as minimax trees and compare the two approaches to see which performs best.

%------------------------------------------------------------------------- 
\SubSection{Why do you believe your approach will work?}

There are previous research papers where genetic programming has been successful for board game playing, for instance \cite{human-competitive_gp}, in which agents playing Backgammon and chess were evolved. Since those games are is somewhat similar to Traversal, especially chess, this indicates that a similar approach should be possible by the same method. Other papers about using genetic programming for board games are \cite{ mancala, othello}.

%------------------------------------------------------------------------ 
\SubSection{What will you accomplish?}

There does not seem to exist any research on Traverse game playing, so building an agent that plays the game well is interesting because it is unexplored territory. Genetic programming is not very widely used within board game playing, and that also makes it interesting to attempt it.

We chose the game Traverse partly for this reason, that it is interesting to investigate a new area, and also because the game has an appropriate level of complexity.

%------------------------------------------------------------------------- 
\section{Survey}

\subsection{Literature}
One paper examining the nature of solvable games is \cite{games_solved}, in which several properties of games are mentioned such as the game-theoretic value (first-player win, second-player win or draw) and whether games are divergent or convergent. The article proposes a matrix of four different categories of games, signifying how hard they are to fully solve, and by what method they can be solvable. As a pre-study in our report, we will reason about how these properties apply to Traverse to anticipate whether the game is feasible to solve with current computational power. Our hypothesis is that it is not solvable, which encourages trying other methods for a playing algorithm, of which one is genetic programming.

In \cite{human-competitive_gp}, genetic programming is used to develop agents that play board games such as Backgammon, chess endgames and a game called Robocode. The different types of genetic operators are discussed, and the steps of a generic genetic programming algorithm are explained. The different approaches within genetic programming are also discussed, such as using a fixed teacher program vis-à-vis implementing coevolution, where programs within a population compete against each other directly. The coevolution strategy is interesting for us, as we have no access to another artificial intelligence that plays the game, unless we construct one ourselves. The article also provides some insight into what terminals and functions they used for the genetic programming algorithms for the different games.

A school project where students were to develop Reversi (also known as Othello) playing agents is described in \cite{othello}. There, terminals and other genetic programming components for Othello are described and methods to evaluate the students' results are described. The different methods are playing against human players, agents of other students, other agents and more.

We will study these previous attempts at using genetic programming for board game agents to get inspiration and hints on how to construct the genetic programming algorithm and how to evaluate our results.

\subsection{Tools and programs}

Several genetic programming frameworks exist for our intended programming language, Java \cite{genpro}, \cite{jgap}, \cite{n-genes}. We will look into some of these and decide on one that seems be useful for our needs. Instead of developing the whole genetic algorithm from scratch, using such a framework will reduce the development time.

\subsection{Benchmarks}

Some conceivable benchmarks are comparing our artificial intelligence with the following:
\begin{itemize}
	\item{An agent that plays completely randomly}
	\item{A simple agent that plays only by one or a few easy strategies}
	\item{The mathematically computed optimal solution. This will most likely only be possible to calculate for very small boards or boards with no opponent and few pieces.}
	\item{Another kind of algorithm, such as minimax search}
	\item{Human players on different levels}
\end{itemize}

In \cite{games_solved}, comparing with human levels of playing is discussed.  The agent is placed in categories for playing at amateur level, grand master level, world champion level, better than any human, and an additional category for games that have been completely solved. Since we do not have access to any human or artificial players of higher level than amateur, we will not be able to compare our program with anything else of these than an amateur level player. We do, however, intend to determine whether it is better, worse or about equal to a human amateur.

As mentioned above, comparing the genetic programming approach to Minimax trees will only be attempted if time allows. Our hopes are that the final program will be consistently better than the random agent, better than the one-strategy agents, and ideally be as good as a novice human player.

%-------------------------------------------------------------------------
\section{Evaluation}

\subsection{How will you measure progress and results?}

Progress will be measured by regularly comparing against the benchmarks above.

\subsection{Are there any standard data sets or benchmarks to evaluate the performance of your application?}

No, we have not found any previous research on Traverse, so no standard metrics exist. We will measure against our benchmarks stated above.


%-----------------------------------------------------------------------
\section{Initial results}

We have made a program where two human players can play against each other. The rules of Traverse are implemented. Next, we will implement the genetic programming algorithm and perhaps the minimax tree for a very small board and few pieces to try it out before going for the full game.


%-----------------------------------------------------------------------
\section{Project management}

\subsection{What are the major tasks to accomplish?}

\begin{enumerate}
	\item{Create prototype program where pieces can be moved regardless of rules}
	\item{Implement the rules}
	\item{Further reading}
	\item{Evaluate whether genetic programming is feasible to solve the task, or another search method should be the focus instead.}
	\item{Implement genetic algorithm for small board, including terminals, functions and fitness function, that develops the game playing algorithm}
	\item{Fully evolved, working game playing algorithm}
	\item{Extend to full game}
	\item{Write final report}	
\end{enumerate}

\subsection{Who will do what?}

In the beginning the group will be divided in two subgroups, where one investigates the genetic programming approach further and the other looks into other search methods such as minimax trees. Erik Levin and Max Ocklind will be studying genetic programming while the other team will consist of Hans Andersson and Erik Axelsson.

\subsection{Try to define a tentative schedule showing when you will start and finish each task}

The initial prototype is done. Implementing the rules will be done this week (w. 19). Reading further about the are should be done continuously throughout the course, and choosing approach should be made by April 25th. The other estimations are less certain, but we will aim to finish the genetic algorithm for a small board by April 28th, the full artificial intelligence by around May 5th and extending the solution to the full game before the prototype release if possible, otherwise before our demo session.

%-----------------------------------------------------------------------
\section{Website}
The project, including a wiki, report drafts and code is published under GNU General Public License v3 and can be found at the following web address:

\url{http://code.google.com/p/mushai/wiki/Start?tm=6}

%\nocite{games_solved, course_book}
\bibliographystyle{proposal}
\bibliography{proposal}

\end{document}
